Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,

Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Solution:

  1. public class Solution {
  2.   public int[] searchRange(int[] nums, int target) {
  3.     int lo = lower(nums, target, 0, nums.length - 1);
  5.     if (lo == -1) {
  6.       return new int[] {-1, -1};
  7.     }
  9.     int hi = upper(nums, target, 0, nums.length - 1);
  11.     return new int[] {lo, hi};
  12.   }
  14.   int lower(int[] nums, int target, int lo, int hi) {
  15.     if (lo > hi) {
  16.       return -1;
  17.     }
  19.     int mid = lo + (hi - lo) / 2;
  21.     if (nums[mid] == target && (mid == 0 || nums[mid - 1] < target)) {
  22.       return mid;
  23.     }
  25.     if (nums[mid] >= target) {
  26.       return lower(nums, target, lo, mid - 1);
  27.     } else {
  28.       return lower(nums, target, mid + 1, hi);
  29.     }
  30.   }
  32.   int upper(int[] nums, int target, int lo, int hi) {
  33.     if (lo > hi) {
  34.       return -1;
  35.     }
  37.     int mid = lo + (hi - lo) / 2;
  39.     if (nums[mid] == target && (mid == nums.length - 1 || target < nums[mid + 1])) {
  40.       return mid;
  41.     }
  43.     if (nums[mid] <= target) {
  44.       return upper(nums, target, mid + 1, hi);
  45.     } else {
  46.       return upper(nums, target, lo, mid - 1);
  47.     }
  48.   }
  49. }